package com.hkb.josephusproblemlib;

/**
 * 有M个人，其编号分别为1－M。这M个人按顺序排成一个圈。
 * 现在给定一个数N，从第一个人开始依次报数，数到N的人出列，
 * 然后又从下一个人开始又从1开始依次报数，
 * 数到N的人又出列．．．如此循环，直到最后所有人出列为止。
 * 输出出列轨迹。
 *
 * @authorwayfoon
 */

public class Reverse {
    private static class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {

        //头节点单列出来，方便形成循环链表
        Node firstNode = new Node(1);
        Node x = firstNode;

        //建立单向链表
        for (int i = 2; i <= 10; i++) {
            x = (x.next = new Node(i));
        }
        //反转单链表
        System.out.println("----------------------反转前-----------------------");
        printLinkTable(firstNode);
        firstNode = reverse(firstNode, null);
        System.out.println();
        System.out.println("-----------------------反转后----------------------");
        printLinkTable(firstNode);

    }

    public static Node reverse(Node node, Node pre) {
        if (node == null) {
            return node;
        }
        // 反转后的头结点
        Node headNode;

        // next为空，说明是尾节点
        if (node.next == null) {
            // 修改next引用
            node.next = pre;
            // 指定反转后的头节点
            headNode = node;
        } else {
            // 非尾节点，继续递归
            headNode = reverse(node.next, node);
            //修改next引用
            node.next = pre;
        }

        return headNode;
    }

    /**
     * 打印链表
     **/
    private static void printLinkTable(Node head) {
        Node node = head;
        while (node != null) {
            System.out.print(node.data);
            System.out.print("-");
            node = node.next;
        }
    }
}
